Analyzing how an environment of a computer system is evolving is essential to ensure reliable and optimal performance from the system. One way of representing the evolution of the system is by using a visual medium such as a graph. For example, a graph can represent snapshots of live objects such as memory, processor, network, or other system resources in a running computer system. A common challenge when using graphs is identifying subsets of graphs that are growing without bound. These graph subsets may eventually cause the system to crash when it exceeds available system resources, such as memory. This problem is known as a memory leak.
Prior art systems have implemented various techniques to address the above graph evolution analysis problem. However, these techniques cannot be applied in many important runtime environments, for example, Java environments, that have restrictions on data collection and environment analysis. The limitations of the prior art are especially evident when analyzing deployed programs. In this setting, there are certain operations that prior art techniques are restricted from performing and many times the assumptions used by the prior art techniques are invalid.
One common restriction of graph evolution analysis is that snapshots of evolving graphs that are analyzed are taken at widely spaced intervals. For example, when analyzing the memory of Java programs, snapshots are usually taken hours apart. These long intervals ensure that a sufficiently long period of evolution is captured, especially when the evolution is slow or intermittent. Long intervals between snapshots are also important if there are other evolutions occurring concurrently with the problematic one. If the interval is too short, the evolution of interest may be drowned out in the background noise of other evolutions. Another common restriction is that the analysis of the program should be performed while the program is executing in its native environment. When a program is executed in a clean-room setting, reproducing the problems of interest during the program's execution is very difficult or impossible.
These restrictions imply that evolution analysis techniques cannot assume that graph nodes have unique and persistent identities. However, prior art techniques have carried these assumptions. These assumptions are difficult to enforce because they impose a large space and time overhead on the program's execution. Some prior art systems have implemented techniques that only assume, without enforcing, persistent identity. These prior art techniques have none of the overhead, but will produce incorrect results when nodes are renamed, for example, by a garbage collector.
Another problem is that prior art techniques that enforce persistent identity usually require modification of the way a program behaves as it executes. The restrictions discussed above, require that on deployed applications these techniques cannot modify how the program behaves as it executes, especially when executing in its native environment.
Yet, another problem is that programs typically have other concurrent mechanisms that periodically rename graph nodes. So even if snapshots were taken over a short enough interval and the overheads confined to that interval, the overheads of persistent identity still cannot be tolerated. For example, in Java, the garbage collector routinely moves objects around, therefore causing the object's address to periodically change. If the renaming period is shorter than the period from first snapshot acquisition to the last snapshot acquisition, persistent objects names are not yielded. To address these naming issues in Java, the header of each object could be augmented with a 64-bit identifier, or the garbage collector could be augmented to notify the analyzing application when an object is renamed. However, these naming strategies have space, time, and configuration implications that limit their applicability to deployed settings. Furthermore, their impact is not confined to the duration of analysis, e.g. if one adds 64 bits to each object, that impact is felt throughout that execution of the program.
Another problem is that the prior art systems for evolution analysis assume persistent node identity. Some techniques, known, collectively as “snapshot differencing” operate as follows. Two snapshots are taken and aligned by corresponding the nodes in the second snapshot with the nodes in the first snapshot. Then an interactive picture of the difference is drawn. For example, the interactive picture shows that a node previously had outgoing edges pointing to two nodes of a certain color and now the node points to three such colored nodes. These differencing techniques only work if nodes can be aligned and the prior art techniques do so by assuming and sometimes enforcing persistent node identity.
Additionally, some prior art systems, in addition to assuming and enforcing persistent node identity provide mechanisms for removing false positives. However, a critical step in false positive removal does not adhere to the in-production restriction discussed above. The validation mechanism operates by taking the generated patterns and modifying the program so as to keep track of how many times each pattern is matched as the program runs. However, this technique does not adhere to the restrictions discussed above because it modifies the program's normal execution.
Therefore a need exists to overcome the problems with the prior art as discussed above.